package com.yww.datastructure.line.linkedlist;

import com.yww.datastructure.line.Linear;

import java.util.Iterator;
import java.util.Objects;
import java.util.function.Consumer;
import java.util.stream.Stream;

/**
 * @author yww
 * @description 双向循环链表
 * @since 2024/1/30 20:03
 */
public final class CircularLinkedList<E> implements Linear<E> {
    // 哨兵，即当头指针，又当尾指针
    // s -> 1 -> 2 -> s
    private final Node<E> sentinel;

    public CircularLinkedList() {
        this.sentinel = new Node<>(null, null, null);

        // 首尾相连
        sentinel.pre = sentinel;
        sentinel.next = sentinel;
    }

    @Override
    public E get(int index) {
        Node<E> node = find(index);
        if (node == null) {
            throw illegalIndex(index);
        }
        return node.val;
    }

    @Override
    public void addLast(E e) {
        // 最后一个节点
        Node<E> last = sentinel.pre;
        // 新节点前指last，后指哨兵
        Node<E> added = new Node<>(last, e, sentinel);
        sentinel.pre = added;
        last.next = added;
    }

    @Override
    public void addFirst(E e) {
        // 首节点
        Node<E> first = sentinel.next;
        // 新节点前指哨兵，后指首节点
        Node<E> added = new Node<>(sentinel, e, first);
        sentinel.next = added;
        first.pre = added;
    }

    @Override
    public void add(E e, int index) {
        // 找到前驱
        Node<E> pre = find(index - 1);
        if (pre == null) {
            throw illegalIndex(index);
        }
        // 新节点的后继
        Node<E> next = pre.next;
        Node<E> added = new Node<>(pre, e, next);
        pre.next = added;
        next.pre = added;
    }

    @Override
    public void foreach(Consumer<E> consumer) {
        Node<E> p = sentinel.next;
        while (p != sentinel) {
            consumer.accept(p.val);
            p = p.next;
        }
    }

    @Override
    public Stream<E> stream() {
        Stream.Builder<E> builder = Stream.builder();
        foreach(builder::add);
        return builder.build();
    }

    @Override
    public E remove(int index) {
        // 找到待删除节点的前驱
        Node<E> pre = find(index - 1);
        if (pre == null) {
            throw illegalIndex(index);
        }
        Node<E> removed = pre.next;
        // 后继
        Node<E> next = removed.next;
        pre.next = next;
        next.pre = pre;
        return removed.val;
    }


    @Override
    public boolean isEmpty() {
        return sentinel.next == sentinel;
    }

    public E removeFirst() {
        Node<E> removed = sentinel.next;
        // 待删除的首节点不能是哨兵节点
        if (removed == sentinel) {
            throw illegalIndex(0);
        }
        Node<E> next = removed.next;
        sentinel.next = next;
        next.pre = sentinel;
        return removed.val;
    }

    @Override
    public int size() {
        Node<E> p = this.sentinel;
        int i = 0;
        while (p.next != sentinel) {
            p = p.next;
            i++;
        }
        return i;
    }

    public E removeLast() {
        Node<E> removed = sentinel.pre;
        // 待删除节点不能是尾节点
        if (removed == sentinel) {
            throw illegalIndex(0);
        }

        Node<E> pre = removed.pre;
        pre.next = sentinel;
        sentinel.pre = pre;

        return removed.val;
    }

    public void removeByVal(E e) {
        // 找到了待删除节点
        Node<E> removed = findByVal(e);
        if (removed == null) {
            return;
        }

        Node<E> next = removed.next;
        Node<E> pre = removed.pre;
        pre.next = next;
        next.pre = pre;
    }

    private Node<E> findByVal(E e) {
        Node<E> p = sentinel.next;

        while (p != sentinel) {
            if (Objects.equals(p.val, e)) {
                return p;
            }
            p = p.next;
        }

        return null;
    }

    private Node<E> find(int index) {
        int i = -1;
        Node<E> p = this.sentinel;

        // index == -1 返回哨兵
        if (index == -1) {
            return sentinel;
        }

        while (p.next != sentinel) {
            // 注意！：要先更新i和p
            i++;
            p = p.next;

            if (index == i) {
                return p;
            }
        }

        return null;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public E next() {
                E res = p.val;
                p = p.next;
                return res;
            }
        };
    }

    private static class Node<E> {
        Node<E> pre;
        E val;
        Node<E> next;

        // 构造器，方便插入
        public Node(Node<E> pre, E val, Node<E> next) {
            this.pre = pre;
            this.val = val;
            this.next = next;
        }
    }
}
